<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<!-- 
	Copyright (C) 2007, 2008, 2009, 2010, 2011. PARP Research Group.
	<http://perception.inf.um.es>
	University of Murcia, Spain.

	This file is part of the QVision library.

	QVision is free software: you can redistribute it and/or modify
	it under the terms of the GNU Lesser General Public License as
	published by the Free Software Foundation, version 3 of the License.

	QVision is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public
	License along with QVision. If not, see <http://www.gnu.org/licenses/>.
-->

<html><head><meta http-equiv="content-Type" content="text/html;charset=UTF-8">
<title>QVision: Qt&#39;s Image, Video and Computer Vision Library</title>
<meta name="title" content="QVision" />
<meta name="dc.title" content="QVision" />
<meta name="url" content="http://perception.inf.um.es/QVision" />
<meta name="author" content="PARP Research Group - http://perception.inf.um.es" />
<meta name="revisit-after" content="30 DAYS"/>
<meta name="robots" content="index,follow"/>
<meta name="classification" content="*">
<meta name="rating" content="Safe For Kids">
<meta name="distribution" content="GLOBAL"/>
<meta name="description" content="Qt's Image, Video and Computer Vision Library"/>
<meta name="page-topic" content="Computer Vision research and prototype programming"/>
<meta name="geo.country" content="ES" />

<!--
Keywords:
By license:		open source, gnu, lgpl, gpl, free
By theme:		computer vision, image processing, robotics, programming, source, development
By usage:		library, toolkit, framework, prototype, application
By programming specs:	object oriented, c++, block programming, reusability, gui, graphical, parallel computing, high performance, GPU, prototyping
Interoperability with:	Qt, GSL, GNU Scientific library, OpenCV, CGAL, QWT, CUDA, mplayer, IPP, Intel Image Performance Primitives, blas, lapack
Functionallity:		image features, matrix algebra, projective geometry, mser, function minimization, function optimization, canny operator, harris operator, corner detection, performance evaluation, cpu usage, graphical interface
Main data-types:	matrix, vector, tensor, quaternion, image, polyline
Video sources:		webcam, camera, stream
Devices:		embedded, desktop computer, laptop, mini-laptop
Authors:		PARP research group. University of Murcia, Spain.
-->

<meta name="keywords" content="augmented reality, sfm, structure from motion, open source, gnu, lgpl, gpl, free, computer vision, image processing, robotics, programming, source, development, library, toolkit, framework, prototype, application, object oriented, c++, block programming, reusability, gui, graphical, parallel computing, high performance, GPU, prototyping, Qt, GSL, GNU Scientific library, OpenCV, CGAL, QWT, CUDA, mplayer, IPP, Intel Image Performance Primitives, blas, lapack, image features, matrix algebra, projective geometry, mser, function minimization, function optimization, canny operator, harris operator, corner detection, performance evaluation, cpu usage, graphical interface, matrix, vector, tensor, quaternion, image, polyline, webcam, camera, stream, embedded, desktop computer, laptop, mini-laptop, University of Murcia, Spain, PARP research group, vision por computador"/>
<meta http-equiv="keywords" content="augmented reality, sfm, structure from motion, open source, gnu, lgpl, gpl, free, computer vision, image processing, robotics, programming, source, development, library, toolkit, framework, prototype, application, object oriented, c++, block programming, reusability, gui, graphical, parallel computing, high performance, GPU, prototyping, Qt, GSL, GNU Scientific library, OpenCV, CGAL, QWT, CUDA, mplayer, IPP, Intel Image Performance Primitives, blas, lapack, image features, matrix algebra, projective geometry, mser, function minimization, function optimization, canny operator, harris operator, corner detection, performance evaluation, cpu usage, graphical interface, matrix, vector, tensor, quaternion, image, polyline, webcam, camera, stream, embedded, desktop computer, laptop, mini-laptop, University of Murcia, Spain, PARP research group, vision por computador"/>
<meta http-equiv="pragma" content="no-cache"/>
<meta http-equiv="title" content="QVision"/>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="tabs.css" rel="stylesheet" type="text/css" />
<link rel="shortcut icon" href="favicon.ico" />
</head><body>

<table width="100%"><tr>
	<td><a href="http://perception.inf.um.es/"><img src="parp.png" border="0" /> <big>PARP Research Group</big></a></td>
	<td align="right"><a href="http://www.um.es/"><big>Universidad de Murcia</big> <img src="um.png" border="0" /></a></td>
</tr></table>

<hr /><br />

<table width="95%" align="center"><tr><td>

<!-- Generated by Doxygen 1.6.3 -->
<script type="text/javascript"><!--
var searchBox = new SearchBox("searchBox", "search",false,'Search');
--></script>
<div class="navigation" id="top">
  <div class="tabs">
    <ul>
      <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
      <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
      <li><a href="modules.html"><span>Modules</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
          <form id="FSearchBox" action="search.php" method="get">
            <img id="MSearchSelect" src="search/search.png" alt=""/>
            <input type="text" id="MSearchField" name="query" value="Search" size="20" accesskey="S" 
                   onfocus="searchBox.OnSearchFieldFocus(true)" 
                   onblur="searchBox.OnSearchFieldFocus(false)"/>
          </form>
        </div>
      </li>
    </ul>
  </div>
  <div class="tabs">
    <ul>
      <li><a href="files.html"><span>File&nbsp;List</span></a></li>
      <li><a href="globals.html"><span>File&nbsp;Members</span></a></li>
    </ul>
  </div>
<h1>src/qvsfm/laSBA/sba-1.6/sba_crsm.c</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 
<a name="l00002"></a>00002 
<a name="l00003"></a>00003 
<a name="l00004"></a>00004 
<a name="l00005"></a>00005 
<a name="l00006"></a>00006 
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 
<a name="l00009"></a>00009 
<a name="l00010"></a>00010 
<a name="l00011"></a>00011 
<a name="l00012"></a>00012 
<a name="l00013"></a>00013 
<a name="l00014"></a>00014 
<a name="l00015"></a>00015 
<a name="l00016"></a>00016 
<a name="l00017"></a>00017 
<a name="l00018"></a>00018 
<a name="l00019"></a>00019 
<a name="l00020"></a>00020 <span class="preprocessor">#include &lt;stdio.h&gt;</span>
<a name="l00021"></a>00021 <span class="preprocessor">#include &lt;stdlib.h&gt;</span>
<a name="l00022"></a>00022 
<a name="l00023"></a>00023 <span class="preprocessor">#include &quot;sba.h&quot;</span>
<a name="l00024"></a>00024 
<a name="l00025"></a>00025 <span class="keyword">static</span> <span class="keywordtype">void</span> sba_crsm_print(<span class="keyword">struct</span> sba_crsm *sm, FILE *fp);
<a name="l00026"></a>00026 <span class="keyword">static</span> <span class="keywordtype">void</span> sba_crsm_build(<span class="keyword">struct</span> sba_crsm *sm, <span class="keywordtype">int</span> *m, <span class="keywordtype">int</span> nr, <span class="keywordtype">int</span> nc);
<a name="l00027"></a>00027 
<a name="l00028"></a>00028 <span class="comment">/* allocate a sparse CRS matrix */</span>
<a name="l00029"></a>00029 <span class="keywordtype">void</span> sba_crsm_alloc(<span class="keyword">struct</span> sba_crsm *sm, <span class="keywordtype">int</span> nr, <span class="keywordtype">int</span> nc, <span class="keywordtype">int</span> nnz)
<a name="l00030"></a>00030 {
<a name="l00031"></a>00031 <span class="keywordtype">int</span> msz;
<a name="l00032"></a>00032 
<a name="l00033"></a>00033   sm-&gt;nr=nr;
<a name="l00034"></a>00034   sm-&gt;nc=nc;
<a name="l00035"></a>00035   sm-&gt;nnz=nnz;
<a name="l00036"></a>00036   msz=2*nnz+nr+1;
<a name="l00037"></a>00037   sm-&gt;val=(<span class="keywordtype">int</span> *)malloc(msz*<span class="keyword">sizeof</span>(<span class="keywordtype">int</span>));  <span class="comment">/* required memory is allocated in a single step */</span>
<a name="l00038"></a>00038   <span class="keywordflow">if</span>(!sm-&gt;val){
<a name="l00039"></a>00039     fprintf(stderr, <span class="stringliteral">&quot;SBA: memory allocation request failed in sba_crsm_alloc() [nr=%d, nc=%d, nnz=%d]\n&quot;</span>, nr, nc, nnz);
<a name="l00040"></a>00040     exit(1);
<a name="l00041"></a>00041   }
<a name="l00042"></a>00042   sm-&gt;colidx=sm-&gt;val+nnz;
<a name="l00043"></a>00043   sm-&gt;rowptr=sm-&gt;colidx+nnz;
<a name="l00044"></a>00044 }
<a name="l00045"></a>00045 
<a name="l00046"></a>00046 <span class="comment">/* free a sparse CRS matrix */</span>
<a name="l00047"></a>00047 <span class="keywordtype">void</span> sba_crsm_free(<span class="keyword">struct</span> sba_crsm *sm)
<a name="l00048"></a>00048 {
<a name="l00049"></a>00049   sm-&gt;nr=sm-&gt;nc=sm-&gt;nnz=-1;
<a name="l00050"></a>00050   free(sm-&gt;val);
<a name="l00051"></a>00051   sm-&gt;val=sm-&gt;colidx=sm-&gt;rowptr=NULL;
<a name="l00052"></a>00052 }
<a name="l00053"></a>00053 
<a name="l00054"></a>00054 <span class="keyword">static</span> <span class="keywordtype">void</span> sba_crsm_print(<span class="keyword">struct</span> sba_crsm *sm, FILE *fp)
<a name="l00055"></a>00055 {
<a name="l00056"></a>00056 <span class="keyword">register</span> <span class="keywordtype">int</span> i;
<a name="l00057"></a>00057 
<a name="l00058"></a>00058   fprintf(fp, <span class="stringliteral">&quot;matrix is %dx%d, %d non-zeros\nval: &quot;</span>, sm-&gt;nr, sm-&gt;nc, sm-&gt;nnz);
<a name="l00059"></a>00059   <span class="keywordflow">for</span>(i=0; i&lt;sm-&gt;nnz; ++i)
<a name="l00060"></a>00060     fprintf(fp, <span class="stringliteral">&quot;%d &quot;</span>, sm-&gt;val[i]);
<a name="l00061"></a>00061   fprintf(fp, <span class="stringliteral">&quot;\ncolidx: &quot;</span>);
<a name="l00062"></a>00062   <span class="keywordflow">for</span>(i=0; i&lt;sm-&gt;nnz; ++i)
<a name="l00063"></a>00063     fprintf(fp, <span class="stringliteral">&quot;%d &quot;</span>, sm-&gt;colidx[i]);
<a name="l00064"></a>00064   fprintf(fp, <span class="stringliteral">&quot;\nrowptr: &quot;</span>);
<a name="l00065"></a>00065   <span class="keywordflow">for</span>(i=0; i&lt;=sm-&gt;nr; ++i)
<a name="l00066"></a>00066     fprintf(fp, <span class="stringliteral">&quot;%d &quot;</span>, sm-&gt;rowptr[i]);
<a name="l00067"></a>00067   fprintf(fp, <span class="stringliteral">&quot;\n&quot;</span>);
<a name="l00068"></a>00068 }
<a name="l00069"></a>00069 
<a name="l00070"></a>00070 <span class="comment">/* build a sparse CRS matrix from a dense one. intended to serve as an example for sm creation */</span>
<a name="l00071"></a>00071 <span class="keyword">static</span> <span class="keywordtype">void</span> sba_crsm_build(<span class="keyword">struct</span> sba_crsm *sm, <span class="keywordtype">int</span> *m, <span class="keywordtype">int</span> nr, <span class="keywordtype">int</span> nc)
<a name="l00072"></a>00072 {
<a name="l00073"></a>00073 <span class="keywordtype">int</span> nnz;
<a name="l00074"></a>00074 <span class="keyword">register</span> <span class="keywordtype">int</span> i, j, k;
<a name="l00075"></a>00075 
<a name="l00076"></a>00076   <span class="comment">/* count nonzeros */</span>
<a name="l00077"></a>00077   <span class="keywordflow">for</span>(i=nnz=0; i&lt;nr; ++i)
<a name="l00078"></a>00078     <span class="keywordflow">for</span>(j=0; j&lt;nc; ++j)
<a name="l00079"></a>00079       <span class="keywordflow">if</span>(m[i*nc+j]!=0) ++nnz;
<a name="l00080"></a>00080 
<a name="l00081"></a>00081   sba_crsm_alloc(sm, nr, nc, nnz);
<a name="l00082"></a>00082 
<a name="l00083"></a>00083   <span class="comment">/* fill up the sm structure */</span>
<a name="l00084"></a>00084   <span class="keywordflow">for</span>(i=k=0; i&lt;nr; ++i){
<a name="l00085"></a>00085     sm-&gt;rowptr[i]=k;
<a name="l00086"></a>00086     <span class="keywordflow">for</span>(j=0; j&lt;nc; ++j)
<a name="l00087"></a>00087       <span class="keywordflow">if</span>(m[i*nc+j]!=0){
<a name="l00088"></a>00088         sm-&gt;val[k]=m[i*nc+j];
<a name="l00089"></a>00089         sm-&gt;colidx[k++]=j;
<a name="l00090"></a>00090       }
<a name="l00091"></a>00091   }
<a name="l00092"></a>00092   sm-&gt;rowptr[nr]=nnz;
<a name="l00093"></a>00093 }
<a name="l00094"></a>00094 
<a name="l00095"></a>00095 <span class="comment">/* returns the index of the (i, j) element. No bounds checking! */</span>
<a name="l00096"></a>00096 <span class="keywordtype">int</span> sba_crsm_elmidx(<span class="keyword">struct</span> sba_crsm *sm, <span class="keywordtype">int</span> i, <span class="keywordtype">int</span> j)
<a name="l00097"></a>00097 {
<a name="l00098"></a>00098 <span class="keyword">register</span> <span class="keywordtype">int</span> low, high, mid, diff;
<a name="l00099"></a>00099 
<a name="l00100"></a>00100   low=sm-&gt;rowptr[i];
<a name="l00101"></a>00101   high=sm-&gt;rowptr[i+1]-1;
<a name="l00102"></a>00102 
<a name="l00103"></a>00103   <span class="comment">/* binary search for finding the element at column j */</span>
<a name="l00104"></a>00104   <span class="keywordflow">while</span>(low&lt;=high){
<a name="l00105"></a>00105     <span class="comment">/* following early termination test seems to actually slow down the search */</span>
<a name="l00106"></a>00106     <span class="comment">//if(j&lt;sm-&gt;colidx[low] || j&gt;sm-&gt;colidx[high]) return -1; /* not found */</span>
<a name="l00107"></a>00107     
<a name="l00108"></a>00108     <span class="comment">/* mid=low+((high-low)&gt;&gt;1) ensures no index overflows */</span>
<a name="l00109"></a>00109     mid=(low+high)&gt;&gt;1; <span class="comment">//(low+high)/2;</span>
<a name="l00110"></a>00110     diff=j-sm-&gt;colidx[mid];
<a name="l00111"></a>00111     <span class="keywordflow">if</span>(diff&lt;0)
<a name="l00112"></a>00112       high=mid-1;
<a name="l00113"></a>00113     <span class="keywordflow">else</span> <span class="keywordflow">if</span>(diff&gt;0)
<a name="l00114"></a>00114       low=mid+1;
<a name="l00115"></a>00115     <span class="keywordflow">else</span>
<a name="l00116"></a>00116       <span class="keywordflow">return</span> mid;
<a name="l00117"></a>00117   }
<a name="l00118"></a>00118 
<a name="l00119"></a>00119   <span class="keywordflow">return</span> -1; <span class="comment">/* not found */</span>
<a name="l00120"></a>00120 }
<a name="l00121"></a>00121 
<a name="l00122"></a>00122 <span class="comment">/* similarly to sba_crsm_elmidx() above, returns the index of the (i, j) element using the</span>
<a name="l00123"></a>00123 <span class="comment"> * fact that the index of element (i, jp) was previously found to be jpidx. This can be</span>
<a name="l00124"></a>00124 <span class="comment"> * slightly faster than sba_crsm_elmidx(). No bounds checking!</span>
<a name="l00125"></a>00125 <span class="comment"> */</span>
<a name="l00126"></a>00126 <span class="keywordtype">int</span> sba_crsm_elmidxp(<span class="keyword">struct</span> sba_crsm *sm, <span class="keywordtype">int</span> i, <span class="keywordtype">int</span> j, <span class="keywordtype">int</span> jp, <span class="keywordtype">int</span> jpidx)
<a name="l00127"></a>00127 {
<a name="l00128"></a>00128 <span class="keyword">register</span> <span class="keywordtype">int</span> low, high, mid, diff;
<a name="l00129"></a>00129 
<a name="l00130"></a>00130   diff=j-jp;
<a name="l00131"></a>00131   <span class="keywordflow">if</span>(diff&gt;0){
<a name="l00132"></a>00132     low=jpidx+1;
<a name="l00133"></a>00133     high=sm-&gt;rowptr[i+1]-1;
<a name="l00134"></a>00134   }
<a name="l00135"></a>00135   <span class="keywordflow">else</span> <span class="keywordflow">if</span>(diff==0)
<a name="l00136"></a>00136     <span class="keywordflow">return</span> jpidx;
<a name="l00137"></a>00137   <span class="keywordflow">else</span>{ <span class="comment">/* diff&lt;0 */</span>
<a name="l00138"></a>00138     low=sm-&gt;rowptr[i];
<a name="l00139"></a>00139     high=jpidx-1;
<a name="l00140"></a>00140   }
<a name="l00141"></a>00141 
<a name="l00142"></a>00142   <span class="comment">/* binary search for finding the element at column j */</span>
<a name="l00143"></a>00143   <span class="keywordflow">while</span>(low&lt;=high){
<a name="l00144"></a>00144     <span class="comment">/* following early termination test seems to actually slow down the search */</span>
<a name="l00145"></a>00145     <span class="comment">//if(j&lt;sm-&gt;colidx[low] || j&gt;sm-&gt;colidx[high]) return -1; /* not found */</span>
<a name="l00146"></a>00146     
<a name="l00147"></a>00147     <span class="comment">/* mid=low+((high-low)&gt;&gt;1) ensures no index overflows */</span>
<a name="l00148"></a>00148     mid=(low+high)&gt;&gt;1; <span class="comment">//(low+high)/2;</span>
<a name="l00149"></a>00149     diff=j-sm-&gt;colidx[mid];
<a name="l00150"></a>00150     <span class="keywordflow">if</span>(diff&lt;0)
<a name="l00151"></a>00151       high=mid-1;
<a name="l00152"></a>00152     <span class="keywordflow">else</span> <span class="keywordflow">if</span>(diff&gt;0)
<a name="l00153"></a>00153       low=mid+1;
<a name="l00154"></a>00154     <span class="keywordflow">else</span>
<a name="l00155"></a>00155       <span class="keywordflow">return</span> mid;
<a name="l00156"></a>00156   }
<a name="l00157"></a>00157 
<a name="l00158"></a>00158   <span class="keywordflow">return</span> -1; <span class="comment">/* not found */</span>
<a name="l00159"></a>00159 }
<a name="l00160"></a>00160 
<a name="l00161"></a>00161 <span class="comment">/* returns the number of nonzero elements in row i and</span>
<a name="l00162"></a>00162 <span class="comment"> * fills up the vidxs and jidxs arrays with the val and column</span>
<a name="l00163"></a>00163 <span class="comment"> * indexes of the elements found, respectively.</span>
<a name="l00164"></a>00164 <span class="comment"> * vidxs and jidxs are assumed preallocated and of max. size sm-&gt;nc</span>
<a name="l00165"></a>00165 <span class="comment"> */</span>
<a name="l00166"></a>00166 <span class="keywordtype">int</span> sba_crsm_row_elmidxs(<span class="keyword">struct</span> sba_crsm *sm, <span class="keywordtype">int</span> i, <span class="keywordtype">int</span> *vidxs, <span class="keywordtype">int</span> *jidxs)
<a name="l00167"></a>00167 {
<a name="l00168"></a>00168 <span class="keyword">register</span> <span class="keywordtype">int</span> j, k;
<a name="l00169"></a>00169 
<a name="l00170"></a>00170   <span class="keywordflow">for</span>(j=sm-&gt;rowptr[i], k=0; j&lt;sm-&gt;rowptr[i+1]; ++j, ++k){
<a name="l00171"></a>00171     vidxs[k]=j;
<a name="l00172"></a>00172     jidxs[k]=sm-&gt;colidx[j];
<a name="l00173"></a>00173   }
<a name="l00174"></a>00174 
<a name="l00175"></a>00175   <span class="keywordflow">return</span> k;
<a name="l00176"></a>00176 }
<a name="l00177"></a>00177 
<a name="l00178"></a>00178 <span class="comment">/* returns the number of nonzero elements in col j and</span>
<a name="l00179"></a>00179 <span class="comment"> * fills up the vidxs and iidxs arrays with the val and row</span>
<a name="l00180"></a>00180 <span class="comment"> * indexes of the elements found, respectively.</span>
<a name="l00181"></a>00181 <span class="comment"> * vidxs and iidxs are assumed preallocated and of max. size sm-&gt;nr</span>
<a name="l00182"></a>00182 <span class="comment"> */</span>
<a name="l00183"></a>00183 <span class="keywordtype">int</span> sba_crsm_col_elmidxs(<span class="keyword">struct</span> sba_crsm *sm, <span class="keywordtype">int</span> j, <span class="keywordtype">int</span> *vidxs, <span class="keywordtype">int</span> *iidxs)
<a name="l00184"></a>00184 {
<a name="l00185"></a>00185 <span class="keyword">register</span> <span class="keywordtype">int</span> *nextrowptr=sm-&gt;rowptr+1;
<a name="l00186"></a>00186 <span class="keyword">register</span> <span class="keywordtype">int</span> i, l;
<a name="l00187"></a>00187 <span class="keyword">register</span> <span class="keywordtype">int</span> low, high, mid, diff;
<a name="l00188"></a>00188 
<a name="l00189"></a>00189   <span class="keywordflow">for</span>(i=l=0; i&lt;sm-&gt;nr; ++i){
<a name="l00190"></a>00190     low=sm-&gt;rowptr[i];
<a name="l00191"></a>00191     high=nextrowptr[i]-1;
<a name="l00192"></a>00192 
<a name="l00193"></a>00193     <span class="comment">/* binary search attempting to find an element at column j */</span>
<a name="l00194"></a>00194     <span class="keywordflow">while</span>(low&lt;=high){
<a name="l00195"></a>00195       <span class="comment">//if(j&lt;sm-&gt;colidx[low] || j&gt;sm-&gt;colidx[high]) break; /* not found */</span>
<a name="l00196"></a>00196 
<a name="l00197"></a>00197       mid=(low+high)&gt;&gt;1; <span class="comment">//(low+high)/2;</span>
<a name="l00198"></a>00198       diff=j-sm-&gt;colidx[mid];
<a name="l00199"></a>00199       <span class="keywordflow">if</span>(diff&lt;0)
<a name="l00200"></a>00200         high=mid-1;
<a name="l00201"></a>00201       <span class="keywordflow">else</span> <span class="keywordflow">if</span>(diff&gt;0)
<a name="l00202"></a>00202         low=mid+1;
<a name="l00203"></a>00203       <span class="keywordflow">else</span>{ <span class="comment">/* found */</span>
<a name="l00204"></a>00204         vidxs[l]=mid;
<a name="l00205"></a>00205         iidxs[l++]=i;
<a name="l00206"></a>00206         <span class="keywordflow">break</span>;
<a name="l00207"></a>00207       }
<a name="l00208"></a>00208     }
<a name="l00209"></a>00209   }
<a name="l00210"></a>00210 
<a name="l00211"></a>00211   <span class="keywordflow">return</span> l;
<a name="l00212"></a>00212 }
<a name="l00213"></a>00213 
<a name="l00214"></a>00214 <span class="comment">/* a more straighforward (but slower) implementation of the above function */</span>
<a name="l00215"></a>00215 <span class="comment">/***</span>
<a name="l00216"></a>00216 <span class="comment">int sba_crsm_col_elmidxs(struct sba_crsm *sm, int j, int *vidxs, int *iidxs)</span>
<a name="l00217"></a>00217 <span class="comment">{</span>
<a name="l00218"></a>00218 <span class="comment">register int i, k, l;</span>
<a name="l00219"></a>00219 <span class="comment"></span>
<a name="l00220"></a>00220 <span class="comment">  for(i=l=0; i&lt;sm-&gt;nr; ++i)</span>
<a name="l00221"></a>00221 <span class="comment">    for(k=sm-&gt;rowptr[i]; k&lt;sm-&gt;rowptr[i+1]; ++k)</span>
<a name="l00222"></a>00222 <span class="comment">      if(sm-&gt;colidx[k]==j){</span>
<a name="l00223"></a>00223 <span class="comment">        vidxs[l]=k;</span>
<a name="l00224"></a>00224 <span class="comment">        iidxs[l++]=i;</span>
<a name="l00225"></a>00225 <span class="comment">      }</span>
<a name="l00226"></a>00226 <span class="comment"></span>
<a name="l00227"></a>00227 <span class="comment">  return l;</span>
<a name="l00228"></a>00228 <span class="comment">}</span>
<a name="l00229"></a>00229 <span class="comment">***/</span>
<a name="l00230"></a>00230 
<a name="l00231"></a>00231 <span class="preprocessor">#if 0</span>
<a name="l00232"></a>00232 <span class="preprocessor"></span><span class="comment">/* returns 1 if there exists a row i having columns j and k,</span>
<a name="l00233"></a>00233 <span class="comment"> * i.e. a row i s.t. elements (i, j) and (i, k) are nonzero;</span>
<a name="l00234"></a>00234 <span class="comment"> * 0 otherwise</span>
<a name="l00235"></a>00235 <span class="comment"> */</span> 
<a name="l00236"></a>00236 <span class="keywordtype">int</span> sba_crsm_common_row(<span class="keyword">struct</span> sba_crsm *sm, <span class="keywordtype">int</span> j, <span class="keywordtype">int</span> k)
<a name="l00237"></a>00237 {
<a name="l00238"></a>00238 <span class="keyword">register</span> <span class="keywordtype">int</span> i, low, high, mid, diff;
<a name="l00239"></a>00239 
<a name="l00240"></a>00240   <span class="keywordflow">if</span>(j==k) <span class="keywordflow">return</span> 1;
<a name="l00241"></a>00241 
<a name="l00242"></a>00242   <span class="keywordflow">for</span>(i=0; i&lt;sm-&gt;nr; ++i){
<a name="l00243"></a>00243     low=sm-&gt;rowptr[i];
<a name="l00244"></a>00244     high=sm-&gt;rowptr[i+1]-1;
<a name="l00245"></a>00245     <span class="keywordflow">if</span>(j&lt;sm-&gt;colidx[low] || j&gt;sm-&gt;colidx[high] || <span class="comment">/* j not found */</span>
<a name="l00246"></a>00246        k&lt;sm-&gt;colidx[low] || k&gt;sm-&gt;colidx[high])   <span class="comment">/* k not found */</span>
<a name="l00247"></a>00247       <span class="keywordflow">continue</span>;
<a name="l00248"></a>00248 
<a name="l00249"></a>00249     <span class="comment">/* binary search for finding the element at column j */</span>
<a name="l00250"></a>00250     <span class="keywordflow">while</span>(low&lt;=high){
<a name="l00251"></a>00251       mid=(low+high)&gt;&gt;1; <span class="comment">//(low+high)/2;</span>
<a name="l00252"></a>00252       diff=j-sm-&gt;colidx[mid];
<a name="l00253"></a>00253       <span class="keywordflow">if</span>(diff&lt;0)
<a name="l00254"></a>00254         high=mid-1;
<a name="l00255"></a>00255       <span class="keywordflow">else</span> <span class="keywordflow">if</span>(diff&gt;0)
<a name="l00256"></a>00256         low=mid+1;
<a name="l00257"></a>00257       <span class="keywordflow">else</span>
<a name="l00258"></a>00258         <span class="keywordflow">goto</span> jfound;
<a name="l00259"></a>00259     }
<a name="l00260"></a>00260 
<a name="l00261"></a>00261     <span class="keywordflow">continue</span>; <span class="comment">/* j not found */</span>
<a name="l00262"></a>00262 
<a name="l00263"></a>00263 jfound:
<a name="l00264"></a>00264     <span class="keywordflow">if</span>(j&gt;k){
<a name="l00265"></a>00265       low=sm-&gt;rowptr[i];
<a name="l00266"></a>00266       high=mid-1;
<a name="l00267"></a>00267     }
<a name="l00268"></a>00268     <span class="keywordflow">else</span>{
<a name="l00269"></a>00269       low=mid+1;
<a name="l00270"></a>00270       high=sm-&gt;rowptr[i+1]-1;
<a name="l00271"></a>00271     }
<a name="l00272"></a>00272 
<a name="l00273"></a>00273     <span class="keywordflow">if</span>(k&lt;sm-&gt;colidx[low] || k&gt;sm-&gt;colidx[high]) <span class="keywordflow">continue</span>; <span class="comment">/* k not found */</span>
<a name="l00274"></a>00274 
<a name="l00275"></a>00275     <span class="comment">/* binary search for finding the element at column k */</span>
<a name="l00276"></a>00276     <span class="keywordflow">while</span>(low&lt;=high){
<a name="l00277"></a>00277       mid=(low+high)&gt;&gt;1; <span class="comment">//(low+high)/2;</span>
<a name="l00278"></a>00278       diff=k-sm-&gt;colidx[mid];
<a name="l00279"></a>00279       <span class="keywordflow">if</span>(diff&lt;0)
<a name="l00280"></a>00280         high=mid-1;
<a name="l00281"></a>00281       <span class="keywordflow">else</span> <span class="keywordflow">if</span>(diff&gt;0)
<a name="l00282"></a>00282         low=mid+1;
<a name="l00283"></a>00283       <span class="keywordflow">else</span> <span class="comment">/* found */</span>
<a name="l00284"></a>00284         <span class="keywordflow">return</span> 1;
<a name="l00285"></a>00285     }
<a name="l00286"></a>00286   }
<a name="l00287"></a>00287 
<a name="l00288"></a>00288   <span class="keywordflow">return</span> 0;
<a name="l00289"></a>00289 }
<a name="l00290"></a>00290 <span class="preprocessor">#endif</span>
<a name="l00291"></a>00291 <span class="preprocessor"></span>
<a name="l00292"></a>00292 
<a name="l00293"></a>00293 <span class="preprocessor">#if 0</span>
<a name="l00294"></a>00294 <span class="preprocessor"></span>
<a name="l00295"></a>00295 <span class="comment">/* sample code using the above routines */</span>
<a name="l00296"></a>00296 
<a name="l00297"></a>00297 main()
<a name="l00298"></a>00298 {
<a name="l00299"></a>00299 <span class="keywordtype">int</span> mat[7][6]={
<a name="l00300"></a>00300     {10, 0, 0, 0, -2, 0},
<a name="l00301"></a>00301     {3,  9, 0, 0,  0, 3},
<a name="l00302"></a>00302     {0,  7, 8, 7,  0, 0},
<a name="l00303"></a>00303     {3,  0, 8, 7,  5, 0},
<a name="l00304"></a>00304     {0,  8, 0, 9,  9, 13},
<a name="l00305"></a>00305     {0,  4, 0, 0,  2, -1},
<a name="l00306"></a>00306     {3,  7, 0, 9,  2, 0}
<a name="l00307"></a>00307 };
<a name="l00308"></a>00308 
<a name="l00309"></a>00309 <span class="keyword">struct </span>sba_crsm sm;
<a name="l00310"></a>00310 <span class="keywordtype">int</span> i, j, k, l;
<a name="l00311"></a>00311 <span class="keywordtype">int</span> vidxs[7], <span class="comment">/* max(6, 7) */</span>
<a name="l00312"></a>00312     jidxs[6], iidxs[7];
<a name="l00313"></a>00313 
<a name="l00314"></a>00314 
<a name="l00315"></a>00315   sba_crsm_build(&amp;sm, mat[0], 7, 6);
<a name="l00316"></a>00316   sba_crsm_print(&amp;sm, stdout);
<a name="l00317"></a>00317 
<a name="l00318"></a>00318   <span class="keywordflow">for</span>(i=0; i&lt;7; ++i){
<a name="l00319"></a>00319     <span class="keywordflow">for</span>(j=0; j&lt;6; ++j)
<a name="l00320"></a>00320       printf(<span class="stringliteral">&quot;%3d &quot;</span>, ((k=sba_crsm_elmidx(&amp;sm, i, j))!=-1)? sm.val[k] : 0);
<a name="l00321"></a>00321     printf(<span class="stringliteral">&quot;\n&quot;</span>);
<a name="l00322"></a>00322   }
<a name="l00323"></a>00323 
<a name="l00324"></a>00324   <span class="keywordflow">for</span>(i=0; i&lt;7; ++i){
<a name="l00325"></a>00325     k=sba_crsm_row_elmidxs(&amp;sm, i, vidxs, jidxs);
<a name="l00326"></a>00326     printf(<span class="stringliteral">&quot;row %d\n&quot;</span>, i);
<a name="l00327"></a>00327     <span class="keywordflow">for</span>(l=0; l&lt;k; ++l){
<a name="l00328"></a>00328       j=jidxs[l];
<a name="l00329"></a>00329       printf(<span class="stringliteral">&quot;%d %d  &quot;</span>, j, sm.val[vidxs[l]]); 
<a name="l00330"></a>00330     }
<a name="l00331"></a>00331     printf(<span class="stringliteral">&quot;\n&quot;</span>);
<a name="l00332"></a>00332   }
<a name="l00333"></a>00333 
<a name="l00334"></a>00334   <span class="keywordflow">for</span>(j=0; j&lt;6; ++j){
<a name="l00335"></a>00335     k=sba_crsm_col_elmidxs(&amp;sm, j, vidxs, iidxs);
<a name="l00336"></a>00336     printf(<span class="stringliteral">&quot;col %d\n&quot;</span>, j);
<a name="l00337"></a>00337     <span class="keywordflow">for</span>(l=0; l&lt;k; ++l){
<a name="l00338"></a>00338       i=iidxs[l];
<a name="l00339"></a>00339       printf(<span class="stringliteral">&quot;%d %d  &quot;</span>, i, sm.val[vidxs[l]]); 
<a name="l00340"></a>00340     }
<a name="l00341"></a>00341     printf(<span class="stringliteral">&quot;\n&quot;</span>);
<a name="l00342"></a>00342   }
<a name="l00343"></a>00343 
<a name="l00344"></a>00344   sba_crsm_free(&amp;sm);
<a name="l00345"></a>00345 }
<a name="l00346"></a>00346 <span class="preprocessor">#endif</span>
</pre></div></div>
</td></tr></table>

<br /><hr><br />
<center><a href="http://perception.inf.um.es/QVision">QVision framework</a>.
<a href="http://perception.inf.um.es">PARP research group</a>.
Copyright &copy; 2007, 2008, 2009, 2010, 2011.</center>
<br />
</body>
</html>
